perm filename ALCOM.POX[HAL,HE]1 blob
sn#187088 filedate 1975-11-19 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00007 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 \F2\{OVERVIEW OF THE AL COMPILER\}=8=3\F0
C00006 00003 \{Parser\}=8=3
C00012 00004 \{Internal Representation of AL Programs\}=8=3
C00015 00005 \{Preprocessor\}=8=3
C00020 00006 \preprocessor continued
C00025 00007 \{Code Emitter\}=8=3
C00034 ENDMK
C⊗;
\F2\{OVERVIEW OF THE AL COMPILER\}=8;=3;\F0
\{Introduction\}=8;=3;
\JThe AL compiler is responsible for translating a user's
AL program into interpreter code that can be executed by the
runtime system. This document gives brief descriptions
of the major components of the compiler and traces the
perils and progress of a simple AL program as it goes
through the various stages of compilation.
The compiler is currently being implemented in SAIL for a
PDP-10. The implementation structure is still essentially the
same as that described in AIM-243, \F1AL, a Programming System for
Automation\F0, although some minor changes have been made.
Translation is accomplished in three phases:\.
\j1.\{Parsing\}=8;=3;. The source text is read in and translated into
an internal structure ("program graph") understandable by
the rest of the compiler.
2. \{Preprocessing\}=8;=3;. The AL program is simulated to build up a
detailed planning model of the expected state at each point
in the program graph. The information in this model will
be used by the code emission/trajectory planning phase and
includes information about the affixment structure and the
expected value of location variables. In addition, a number
of important details are filled into the program graph,
which may be rewritten somewhat. For instance, affixment statements
are translated into sequences of lower-level "graph assignment"
statements. Similarly, the modeled affixment structure is
used to turn statements like "MOVE a TO b" into more explicit
statements involving a specific arm, like "MOVE BARM TO b*t".
3. \{Code emission\}=8;=3;. Joint trajectories are computed for all
motion statements, based on the expected location values contained
in the planning model. These trajectories are written into
output files. Similarly, interpreter code is produced from
the refined program graph and written into an output file.\.
\JSubsequent sections will describe these phases in more detail.
The principal differences with AIM-243
are the input syntax, for which a much simpler form
is currently being used, and the compiler output format, which
is now a text file for input to a PDP-11 assembler, rather than
a binary load module.\.
\{Parser\}=8;=3;
\JThe parser is responsible for translating the user's source program
into a form that can be manipulated conveniently by the rest of the
compiler. Although the AL syntax does offer some moderately interesting
problems (for instance, physical units checking and expression variables),
implementation of a parser for the syntax given in AIM-243 was
postponed until such time as a volunteer could be found to do the work.
(Actually, a table-driven parser for AL was written some time ago. The
productions were never completely debugged, however, and the program
was abandoned for want of a person to work on it).
Instead, a much simpler input syntax has been substituted as an interim
measure.
The basic elements in this syntax
are atomic symbols and forms like:\.
\!narrow;
(<keyword> <e1> <e2> ... <ek> )
\!widen;
\Jwhich correspond in a more or less one-to-one manner with the record
structures used inside the compiler. For instance, the program\.
\!narrow;
BEGIN
FRAME a,b;ROTN r;TRANS t;
r←ROT(YHAT,180*DEG);
a ← FRAME(r,VECTOR(0,0,2));
MOVE YELLOW TO FRAME(r,VECTOR(1,0,2));
b ← FRAME(r,VECTOR(0,0,3));
AFFIX a TO YELLOW BY t RIGIDLY;
MOVE a TO b;
MOVE a TO b*TRANS(ROT(XHAT,90*DEG),VECTOR(1,1,1));
UNFIX a FROM YELLOW;
MOVE YELLOW TO YPARK;
END;
\!widen;
would be written as
\!narrow;
(PR
(BL (FVAR a b)(RVAR r)(TVAR t)
(AS r (RMAKE YHAT (SSMUL 180 DEG)))
(AS a (FMAKE r (VMAKE 0 0 2)))
(MO YARM (FMAKE r (VMAKE 1 0 2)))
(AS b (FMAKE r (VMAKE 0 0 3)))
(AFFIX a YARM t () RIGIDLY)
(MO a b)
(MO a (TTMUL b (TMAKE (AXW_ROTN XHAT (SSMUL 90 DEG))(VMAKE 1 1 1))))
(UNFIX a YARM)
(MO YARM YPARK)
)
)
\!widen;
\JA simple parser for the simplified syntax has been implemented and
incorporated into the present compiler implementation, and an interim
programming manual has been written for persons wishing to use
AL in its present form. (The manual is reprinted in another section
of this report).
Generally speaking, the semantics of the various language constructs have
remained pretty much the same as given in AIM-243. Only the names have
been changed. This approach has permitted effort to be concentrated
on the more important problems of producing a working runtime system
and building programs to transform AL program structures into code
that can be interpreted by the runtime system.
Recently, Mr. W. T. Laaser (a Computer Science graduate student at Stanford) has
begun work on a parser for the AIM-243 syntax. The tentative approach
taken for this is to translate source text into the corresponding
AL internal structures and then to translate the internal structures
into a text file that can be read in by the present parser. One of the
principal advantages of this approach is that it
insulates the parser project from
work on the rest of the compiler, thus keeping bugs occuring in one part
from holding up work in the other. The danger, of course, is that
the structures built by the parser may be subtly different from those
used in the compiler, thus making it very difficult to do away eventually
with the intermediate file. We are aware of this, and are taking care to
minimize any such difficulties. In any event, it is felt that the possible
costs of later merging are more than compensated by the benefits of
increased insulation during program development.
\.
\,
\{Internal Representation of AL Programs\}=8;=3;
\JInternally, AL program graphs are built as SAIL record structures.
Essentially, the compiler associates
a record "class" with each major semantic entity in AL. For example:\.
\F3
RECORD_CLASS V3ECT(REAL X,Y,Z);
RECORD_CLASS ASSIGNMENT(POINTER(VARIABLE) VAR;POINTER(EXPRESSION) VAL);
\F0
\Jare used for vector constants and assignment statements, respectively.
Component elements of the records can then be accessed by name, as
with:\.
\F3
Q←V3ECT:X[V1]*V3ECT:X[V2];
\F0
\JA large number of "service" routines have been provided to aid in
manipulating these structures. For instance,\.
\F3
HALPRN(<structure>) -- produces "pretty printed" output of <structure>
V3DOT(V1,V2) -- computes the vector dot product of V1 and V2
\F0
\JThis approach has allowed considerable flexibility in implementation,
since SAIL handles all free-storage management and
since new attributes can be added to the various semantic entities
without recoding previously debugged programs.
Currently, there are in excess of 50 such class declarations,
new ones being added at a rate of (very) roughly two a week.
The principal structural entities used in representing an AL program
are BLOCK and STMNT records. Simpilfied, their declarations look like
this:\.
\F3
RECORD_CLASS BLOCK(LIST CODE,VARS);
RECORD_CLASS STMNT(ITEM IW,OW;POINTER(ANY_CLASS) SEMANTICS);
\F0
\JIn a BLOCK, VARS is a list of variables declared within that block,
and code is a list of STMNT records for the executable statements
in the block. In a statement, IW and OW are context pointers into
the simulation model's data base, corresponding, respectively, to the expected
state before and after the statement is executed. Figure 1 illustrates
the program graph built for our sample program.
\.
\{Preprocessor\}=8;=3;
\JThe principal duty of the preprocessor is to produce a "planning
model" of the expected program state at each point in the program
graph. This model is then used to supply planning values for
use by the trajectory calculator, to determine which arm is to
be used in motion statements, and other similar purposes.
The planning model is kept in a data base of assertional forms, the
most important of which (for our present purposes) are those dealing
with expected values and affixments, for example:\.
\F3
(VALUE_OF_YARM,FRAME(NILROT,VECTOR(0,31.2,23.7))
(AFFIXED,f1,YARM,t,NONRIGIDLY)
\F0
\JWith each such assertion, the database routines keep a list of
"worlds" in which that assertion is assumed to be "true".
Currently, the data base routines
include facilities for addition, deletion, and associative retrieval
of facts from the data base and for manipulating worlds as if they
were sets of facts. The principal routines include:\.
\F3
ASRTPF(<world>,<form>) -- adds assertional form to <world>
DENYPF(<world>,<form>) -- removes assertional form from <world>
PMATCH(<world>,<form>) -- retrieves all forms that match <form> in <world>
CPYWLD(<world 1>,<world 2>) -- makes a fact true in <world 2> if and only if it\N
is true in <world 1>
ANDWLD(<world 1>,<world 2>,<world 3>) -- sets <world 2> to the intersection\;
of <world 1> and <world 2>.
ANDWLD(<world 1>,<world 2>,<world 3>) -- sets <world 2> to the union\;
of <world 1> and <world 2>.
\F0
\JOther routines provide a "demon" facility that allows a pattern to be flagged
so that additional book-keeping procedures are called whenever that pattern
is asserted or denied.
Subroutines for simulating the effects of graph structure are built "on top
of" the database routines. These
include:\.
\F3
GETVALUE(<variable>,<world>) -- returns planning value of <variable> in <world>
VCHANGE(<variable>,<value>,<world>) -- sets the planning value of <variable>\N
to <value> in <world>
EVALEXPR(<expression>,<world>) -- computes planning value for <expression> \N
in <world>.
\F0
\Jwhich are used by both the simulator and the trajectory calculator to fetch
planning values. Other important graph structure routines in EXPRS include
ADDCLC, KILLCLC, ADDCHG, and KILLCHG, which are used in simulating graph structure
modifications.
The actual simulation proceeds in two phases:\.
\!narrow;
\J1.\{initialization\}=8;=3; Procedure WLDASG is called to assign input and output planning worlds to
every statement in the program graph. Usually, the output world of
one statement will be the input world of the next statement. To avoid needless
proliferation of worlds, WLDASG treats sequences of assignments and affixments
as a single statement.
In addition, initial planning values are set up for certain predeclared variables
(such as YARM). World assignments for our sample program are indicated below.\.
\;preprocessor continued
\!narrow;\F3
(PR
(BL (FVAR a b)(RVAR r)(TVAR t)
(AS r (RMAKE YHAT (SSMUL 180 DEG))) [IW = W0, OW = W1]
(AS a (FMAKE r (VMAKE 0 0 2))) [IW = W1, OW = W1]
(MO YARM (FMAKE r (VMAKE 1 0 2))) [IW = W1, OW = W2]
(AS b (FMAKE r (VMAKE 0 0 3))) [IW = W2, OW = W3]
(AFFIX a YARM t () RIGIDLY) [IW = W3, OW = W3]
(MO a b) [IW = W3, OW = W4]
(MO a (TTMUL b (TMAKE (AXW_ROTN XHAT (SSMUL 90 DEG))(VMAKE 1 1 1)))) [IW = W4, OW = W5]
(UNFIX a YARM) [IW = W5, OW = W6]
(MO YARM YPARK) [IW = W6, OW = W7]
)[IW = W0, OW = W7]
)
\!widen;\F0
\J2.\{simulation\}=8;=3; Recursive procedure STINTERP is called to perform the
actual smulation. This procedure consists of a big IF-THEN-ELSE chain
that looks at the semantics of each statement and performs the appropriate
actions to update the planning model. Typically, this involves copying
the input world into the output world and then modifying the output
world to reflect any changes introduced by the statement. STINTERP is
capable of handling all the AL control structures currently implemented,
including conditionals, coblocks, and loops. In addition to building
the planning model, STINTERP makes a number of minor modifications to the
program graph. These include invention of temporary variables, translation
of AFFIX and UNFIX statements into the corresponding graph modification
statements, and rewriting MOVE statements to always be in terms of an arm.
Procedures for larger modifications, such as "unrolling" of loops or
translation of "very high level" statements into manipulator commands,
are not included in the version presently integrated into the compiler.\.
\!widen;
\JOnce preprocessing is complete, the planning model's data base will contain
the data needed by the trajectory calculator. For our test case, the data base
will contain assertions that look roughly like the following:\.
\!narrow;\F3
(AFFIXED,a,YARM,t,RIGIDLY) in W3,W4,W5
(AFFIXED,YARM,a,(TINVRT t),RIGIDLY) in W3,W4,W5
...
(COMPUTES_a,(TTMUL YARM t)) in W3,W4,W5
...
(VALUE_OF_a,FRAME(ROT(YHAT,180*DEG),VECTOR(0,0,2)) in W1,W2,W3
(VALUE_OF_a,FRAME(ROT(YHAT,180*DEG),VECTOR(0,0,3)) in W4
...
\!widen;\F0
\JIn addition, the AFFIX statement will have been annotated to indicate that
it should be compiled as:\.
\!narrow;\F3
(AS t (TTMUL (TINVRT YARM) a))
(GAS a = (g001 CLC (TTMUL YARM t)))
(GAS YARM = (g002 CLC (TTMUL a (TINVRT t))))
\!widen;\F0
The UNFIX will be annotated for expansion as
\!narrow;\F3
(GAS a ≠ g001)
(GAS YARM ≠ g002)
\!widen;\F0
\Jand the move statements will be rewritten explicitly in terms of the
yellow arm. For instance, (MO a b) in our example would be rewritten
as (MO YARM (TTMUL b (TINVRT t))).\.
\,
\{Code Emitter\}=8;=3;
\JThere are three major components in the code emission phase:
a code generator, which translates internal structures into the
proper interpreter pseudo-code, the trajectory calculator, and
a function that does the actual work of writing the output file.\.
\F1\{code generator\}=8;=3;
\F0\JThe principal routine is TSCAN, which generates code for the root of
the bound parse tree and calls itself recursively for the rest.
TSCAN is a large IF-THEN-ELSE-IF-THEN chain which determines which of
the various possible structures is present. If it is some kind of
statement, then appropriate pseudo-code is emitted. The preparation
of this code may require that code for the evaluation of an
expression. Such code is prepared in the recursive procedure
EMITEXPR, which performs type-consistency checking (but not constant
folding, which could be done here). Code for boolean tests is
prepared by EMITBOOL.\.
\F1\{trajectory calculator\}=8;=3;
\F0\JThe trajectory calculator turns motion specifications into
interpretable tables. At the moment it allows any one mechanism,
that is, one arm or one hand. Future work will allow any combination
of mechanisms. The tables are calculated by the following method:\.
\jA thread is made, with a node for each place in the motion
specification, that is, the initial point, the departure, if any, the
via points, the approach point, and the destination. Arm or hand
solutions are calculated for each node. It may be that this serial
calculation will lead to flips of the arm. If this happens, the
proper order is outside-in. This is because the ARMSOL routine uses
the previous solution to resolve ambiguities in joint 4 of the
Scheinman arms.\.
\jAny deproach points or calculated via points or calculated
destinations must have code emitted to make a cell for them in the
graph structure. The cell for a departure is marked permanently
invalid. Its calculator uses the hand position itself, not the place
where the arm was to be at the start of the motion. The cells for
the calculated via points and the approach point are in the graph
structure in the usual way. This code must be emmitted at the
outermost practical point in the program: If it is too far in, then
it gets redone too often, and if it is too far out, it might cause
graph structure to hang around associated to non-existent nodes. In
any case, it is necessary to put such code at a block entry, and to
be sure to get rid of the resulting graph structure at block exit.
The current code does not handle any of this.\.
\jAt this time, the fourth degree polynomials for deproach segments are
calculated, and any given velocity constraints are noted. The
presence of a velocity constraint implies that the acceleration is
constrained to zero. If the user has supplied a time, it is put in
UTIME, and STIME is computed by the system. If they are compatible,
STIME is modified to the final decision on the time for the segment.\.
\jAfter the entire thread is made, a global check is made to insure
that the timing is in agreement with the user's wishes. Then the
thread is divided into chunks, where each chunk is the region between
two velocity-constrained points (the deproach points are such). A
chunk which has only two points (but not a deproach chunk, for which
the trajectory has already been calculated) gets a fifth-degree
polynomial calculated to match all the constraints. A chunk with
more points requires splining for the trajectory. The first step is
to insert one unconstrained point in each of the two longest
intervals. It has been found that the best place for these points is
almost at the very end of the intervals (.999 of the way to the end)
to minimize overshoot problems. After the fully unconstrained nodes
have been inserted into the thread, the routine POLY is called to
create the coefficients of the third degree splined polynomial. It
has been found that using fourth degree polynomials in two of the
segments instead of inserting two unconstrained points leads to
uncontrollable overshoot. Finally, the resulting trajectory is
emitted.\.
\JThe following conventions are used for arms and joints. Joints 1-6
are yellow arm (arm 0), and joint 7 is the yellow fingers (arm 2).
Joints 8-13 are the blue arm (arm 1), and joint 14 is the blue
fingers (arm 3). The angle arrays are tailored to have whatever
joints are needed. The arm and hand solution programs are told which
mechanism to expect.\.
\JThe current code does not check location, velocity or acceleration
bounds except for location bounds at user-specified places. Instead,
location bounds are to a large extent insured by the servo. Velocity
and acceleration can be optimized by rescaling time, in the cases
when the user has not specified any time in the entire motion, nor
any velocities, but this is not currently attempted.\.
\F1\{output function\}=8;=3;
\F0\JAll code emission is done through the routine EMIT which takes
arguments specifying what output file to use (e.g., pseudo-code or
constant area), the data to output, and whether to treat it as an
instruction, an octal constant, a label declaration, or repeatedly to
produce the rel file.
At present, output is generated as text, in the form of symbolic
operation codes and literal numbers. This text is then run through
a standard PDP-11 assembler to produce binary load modules.
\.